/*
 * Copyright (c) 2022.版权所有高金磊
 */

package 领扣算法.力扣计划.算法基础.在排序数组中查找元素;

public class Main {
    public int[] searchRange(int[] nums, int target) {
        //二分查找
        int index=find(nums,target);
        int[] res =new int[2];
        if (index==-1)
            return new int[]{-1,-1};
        if (nums[nums.length-1]==target){
            res[1]=nums.length-1;
        }
        else {
            for (int i = index+1; i < nums.length ; i++) {
                if (nums[i]!=target){
                    res[1]=i-1;
                    break;
                }
            }
        }
        if (nums[0]!=target){
            for (int i = index-1; i >= 0; i--) {
                if (nums[i]!=target){
                    res[0]=i+1;
                    break;
                }
            }
        }
        return res;
    }

    private int find(int[] nums, int target) {
        int small=0;
        int big=nums.length-1;
        int middle=0;
        while (small<big){
            middle=small+(big-small)/2;
            if (nums[middle]==target)
                return middle;
            if (nums[middle]<target){
                small=middle+1;
            }
            else {
                big=middle-1;
            }
        }
        if (nums.length>0&&nums[small]==target)
            return small;
        return -1;
    }
}
